const instance = [3, 6, 0, 9, 1, 2, 5]

// 1. 冒泡排序 - 比较相邻的两个值 过于笨重,比选择排序还笨
function maopao(source) {
  for (let i = 0; i < source.length; i++) {
    for (let j = 0 ; j < source.length; j++) {
      if (source[j] > source[j+1]) {
        let temp = source[j]
        source[j] = source[j+1]
        source[j+1] = temp
      }
    }
  }
  return source
}

console.log('--- 冒泡排序 ---', maopao(instance))

// 2. 选择排序 - 通过每一次的比较选出最小或者最大的放在首位、第二位、第i位...以此类推
function xuanze(source) {
  for (let i = 0 ; i < source.length; i++) {
    for (let j = i + 1; j < source.length; j++) {
      if (source[i] > source[j]) {
        let temp = source[i]
        source[i] = source[j]
        source[j] = temp
      }
    }
  }
  return source
}

console.log('--- 选择排序 ---', xuanze(instance))

// 3. 快速排序 - 将数组取出中间值，以它为基准，按照大小分为两个数组，而后合并并递归这两个数组，直到数组长度小于等于1
function kuaisu (source) {
  if (source.length <= 1) {
    return source
  }

  const [middle] = source.splice(Math.floor(source.length / 2), 1)
  let right = []
  let left = []
  for (let item of source) {
    if (item > middle) {
      right.push(item)
    } else {
      left.push(item)
    }
  }

  return kuaisu(left).concat(middle, kuaisu(right))
}

console.log('---- 快速排序 ---', kuaisu(instance))

// 4. 插入排序

// 5. 希尔排序

// 6. 归并排序

// 7. 堆排序

// 8. 桶排序

// 9. 基数排序
